#ifndef __BINARY_TREE_ORDER__
#define __BINARY_TREE_ORDER__

#include <stack>
#include <deque>

    template <typename P, typename F>
void preOrderTraversal(P binaryTree, F func)
{
    if (!binaryTree)
        return;

    using BinaryTreePointer = P;
    std::stack<BinaryTreePointer> stack;

    while(binaryTree || !stack.empty()) {

        while(binaryTree) {
            stack.push(binaryTree);
            func(binaryTree);
            binaryTree = binaryTree->left;
        }

        if(!stack.empty()) {
            binaryTree = stack.top();
            stack.pop();
            binaryTree = binaryTree->right;
        }
    }
}

    template <typename P, typename F>
void inOrderTraversal(P binaryTree, F func)
{
    if (!binaryTree)
        return;

    using BinaryTreePointer = P;
    std::stack<BinaryTreePointer> stack;

    while(binaryTree || !stack.empty()) {

        while(binaryTree) {
            stack.push(binaryTree);
            binaryTree = binaryTree->left;
        }

        if(!stack.empty()) {
            binaryTree = stack.top();
            stack.pop();
            func(binaryTree);
            binaryTree = binaryTree->right;
        }
    }
}

    template <typename P, typename F>
void postOrderTraversal(P binaryTree, F func)
{
    if (!binaryTree)
        return;

    using BinaryTreePointer = P;
    std::stack<BinaryTreePointer> stack;

    do {
        while (binaryTree) {
            stack.push(binaryTree);
            binaryTree = binaryTree->left;
        }

        BinaryTreePointer lastNode = BinaryTreePointer();

        while (!stack.empty()) {
            binaryTree = stack.top();
            stack.pop();
            if (binaryTree->right == lastNode) {
                func(binaryTree);
                lastNode = binaryTree;
            } 
            else {
                stack.push(binaryTree);
                binaryTree = binaryTree->right;
                break;
            }
        }
    } while (!stack.empty());

    return;
}

    template <typename P, typename F>
void levelOrderTraversal(P binaryTree, F func)
{
    if(!binaryTree)
        return;

    using BinaryTreePointer = P;
    std::deque<BinaryTreePointer> deque;
    deque.push_back(binaryTree);

    while(!deque.empty()) {
        binaryTree = deque.front();
        deque.pop_front();

        func(binaryTree);

        if(binaryTree->left) {
            deque.push_back(binaryTree->left);
        }

        if(binaryTree->right) {
            deque.push_back(binaryTree->right);
        }
    }
}

#endif
